export class QPoint {
    public x:number;
    public y:number;
    public get w():number {return this.x;}
    public get h():number {return this.y;}
    constructor(x:number,y:number){
        this.x = x;
        this.y = y;
    }
}

export class QRect {
    public origin:QPoint;
    public size:QPoint;

    public get centerX():number{ return this.origin.x + this.size.w * 0.5;}
    public get centerY():number{ return this.origin.y + this.size.h * 0.5;}
    public get xMin():number{return this.origin.x };
    public get yMin():number{return this.origin.y };
    public get xMax():number{return this.origin.x + this.size.w};
    public get yMax():number{return this.origin.y + this.size.h};

    public static intersects( rect:QRect, target:QRect):boolean{
		if( rect.yMin > target.yMax ){
            return false;
        }
        if( rect.yMax < target.yMin ){
            return false;
        }
        if( rect.xMax < target.xMin ){
            return false;
        }
        if( rect.xMin > target.xMax ) {
            return false;
        }
        return true;
    }

    constructor(origin:QPoint,size:QPoint){
        this.origin = origin;
        this.size = size;
    }
    
}

class LinkQuadTreeNode<T> {
    public next:LinkQuadTreeNode<T>;
    public treeNode:QuadTreeNode<T>;
    constructor(treeNode:QuadTreeNode<T> = null){
        this.treeNode = treeNode;
    }

    public copy(other:LinkQuadTreeNode<T>){
        this.next = other.next;
        this.treeNode = other.treeNode;
    }
}

class DataNode<T> {
    public data:T;
    public rect:QRect;
    public depth:number;
    public lastLinkTreeInfo:LinkQuadTreeNode<T> = new LinkQuadTreeNode<T>();
    public curLinkTreeInfo:LinkQuadTreeNode<T> = new LinkQuadTreeNode<T>();

    constructor(data:T,depth:number,rect:QRect){
        this.data = data;
        this.depth = depth;
        this.rect = rect;
    }

    public get isLinkChange():boolean{
        let t1 = this.lastLinkTreeInfo.next;
        let t2 = this.curLinkTreeInfo.next;
        while(t2){
            if(t1 != t2){
                return true;
            }
            t1 = t1.next;
            t2 = t2.next;
        }
        return false;
    }
}


class QuadTreeNode<T>{
    protected curDepth:number;
    protected nodesConut:number;
    protected originX:number;
    protected originY:number;
    protected treeNodes:QuadTreeNode<T>[] = [];
    protected children:DataNode<T>[] = [];
    protected rootTree:QuadTree<T>;
    private static looseRectTmp:QRect = new QRect(new QPoint(0,0),new QPoint(0,0));
    
    /**
     * 仅用来读
     */
    public get looseRect():QRect{
        let size = this.rootTree.getSizeByDepth(this.curDepth);
        QuadTreeNode.looseRectTmp.origin.x = this.originX - size.w/2;
        QuadTreeNode.looseRectTmp.origin.y = this.originY - size.h/2;
        QuadTreeNode.looseRectTmp.size.x = size.x * 2;
        QuadTreeNode.looseRectTmp.size.y = size.y * 2;
        return QuadTreeNode.looseRectTmp;
    }

    public get isLeaf():boolean{ return this.rootTree.isMaxDepth(this.curDepth);}

    constructor(originX:number,originY:number,curDepth:number,rootTree:QuadTree<T>){
        this.originX = originX;
        this.originY = originY;
        this.curDepth = curDepth;
        this.rootTree = rootTree;
        this.nodesConut = 0;
        !this.isLeaf && this.splitQuadTree();
    }
    

    /**
     * 四叉树节点
     */
    splitQuadTree(){
        let depth = this.curDepth+1;
        let size = this.rootTree.getSizeByDepth(depth);
        //left bottom
        let treeNode = new QuadTreeNode<T>(this.originX,this.originY,depth,this.rootTree);
        this.treeNodes.push(treeNode);
        //right bottom
        treeNode = new QuadTreeNode<T>(this.originX+size.w,this.originY,depth,this.rootTree);
        this.treeNodes.push(treeNode);
        //left up
        treeNode = new QuadTreeNode<T>(this.originX,this.originY+size.h,depth,this.rootTree);
        this.treeNodes.push(treeNode);
        //right up
        treeNode = new QuadTreeNode<T>(this.originX+size.w,this.originY+size.h,depth,this.rootTree);
        this.treeNodes.push(treeNode);
    }

    /**
     * 更新链接索引路径
     * @param centerX 
     * @param centerY 
     * @param maxDepth 
     * @param linkInfo 
     */
    updatePosInfo(centerX:number,centerY:number,maxDepth:number,linkInfo:LinkQuadTreeNode<T>){
        if(this.curDepth+1 > maxDepth){
            return;
        }
        let size = this.rootTree.getSizeByDepth(this.curDepth+1);
        let row = Math.min(1,Math.floor((centerY - this.originY) / size.h));
        row = Math.max(0,row);
        let col = Math.min(1,Math.floor((centerX - this.originX) / size.w));
        col = Math.max(0,col);
        let idx = row * 2 + col;
        let treeNode = this.treeNodes[idx];
        let nextInfo = new LinkQuadTreeNode<T>(treeNode);
        linkInfo.next = nextInfo;
        treeNode.updatePosInfo(centerX,centerY,maxDepth,nextInfo);
    }


      /**
     * 查询碰撞节点
     * @param rect 
     * @param outItms 接收数组
     * @param outVisItms 访问过的节点
     */
     quary(rect:QRect,outItms:T[],outVisItms:T[]){
        let queue:QuadTreeNode<T>[] = [];
        if(this.checkNeedVisit(rect)){
            queue.push(this);
        } 

        let index = 0;
        while(index < queue.length){
            let treeNode = queue[index]
            for(let i=0 , n=treeNode.children.length ; i<n;i++){
                let dataNode = treeNode.children[i];
                outVisItms.push(dataNode.data);
                if(QRect.intersects(dataNode.rect,rect)){
                    outItms.push(dataNode.data);
                }
            }

            if(!treeNode.isLeaf){
                for(let i=0, n = treeNode.treeNodes.length; i<n ; i++){
                    if(treeNode.treeNodes[i].checkNeedVisit(rect)){
                        queue.push(treeNode.treeNodes[i]);
                    } 
                }
            }
            index++;
        }
    }

     /**
      * 更新四叉树
      * @param item 
      * @param rect 
      */
    update(item:T,rect:QRect){
        let dataNode:DataNode<T> = item["$dataNode"];
        //插入
       if(!dataNode){
            let tmpDepth = this.rootTree.getDepthBySize(rect.size.w,rect.size.h);
            dataNode = new DataNode<T>(item,tmpDepth,rect);
            item["$dataNode"] = dataNode;
       }else{
           dataNode.rect = rect;
       }
       dataNode.curLinkTreeInfo.treeNode = this;
       dataNode.curLinkTreeInfo.next = null;
       this.updatePosInfo(dataNode.rect.centerX,dataNode.rect.centerY,dataNode.depth,dataNode.curLinkTreeInfo);
       if(dataNode.isLinkChange){
           this.remove(dataNode);
           this.insert(dataNode);
           dataNode.lastLinkTreeInfo.copy(dataNode.curLinkTreeInfo);
       }
    }

    /**
     * 插入节点
     * @param dataNode 
     */
    insert(dataNode:DataNode<T>){
        let linkInfo = dataNode.curLinkTreeInfo;
        while(linkInfo && linkInfo.treeNode){
            linkInfo.treeNode.nodesConut ++;
            if(!linkInfo.next){
                linkInfo.treeNode.children.push(dataNode);
            }
            linkInfo = linkInfo.next;
        }
    }

    /**
     * 移除节点
     * @param dataNode 
     */
    remove(dataNode:DataNode<T>){
        let linkInfo = dataNode.lastLinkTreeInfo;
        while(linkInfo && linkInfo.treeNode){
            linkInfo.treeNode.nodesConut --;
            if(!linkInfo.next){
                let index = linkInfo.treeNode.children.indexOf(dataNode);
                linkInfo.treeNode.children.splice(index, 1);
            }
            linkInfo = linkInfo.next;
        }
    }


    private checkNeedVisit(rect:QRect){
        return this.nodesConut > 0 &&  QRect.intersects(this.looseRect,rect);
    }
}


/**
 * 松散网格型四叉树
 */
export default class QuadTree<T>{
    public maxDepth:number;
    public gridMinWidth:number;
    public gridMinHeight:number;
    public depthSize:QPoint[] = [];
    protected quadTreeNode:QuadTreeNode<T>;

    public getSizeByDepth(dep:number):QPoint{
        return this.depthSize[dep];
    }

    public isMaxDepth(depth:number):boolean{
        return depth >= this.maxDepth -1;
    }

    private disDepth(width:number,height:number):number{
        let dw = Math.max(0,Math.floor(Math.log2(width / this.gridMinWidth + 1)));
        let dh = Math.max(0,Math.floor(Math.log2(height/ this.gridMinHeight + 1)));
        return Math.max(dw,dh);
    }

    public getDepthBySize(width:number,height:number):number{
        let disDepth = this.disDepth(width,height);
        return this.maxDepth - disDepth - 1;
    }

   /**
    * 
    * @param originX 左下角x
    * @param originY 左下角y
    * @param conWidth 宽度
    * @param conHeight 高度
    * @param checkMinWidth 检测的物体的最小宽度
    */
    constructor(originX:number,originY:number,conWidth:number,conHeight:number,checkMinWidth:number){
        this.gridMinWidth = checkMinWidth;
        this.gridMinHeight = checkMinWidth;
        this.maxDepth = this.disDepth(conWidth,conHeight);
        let tmp = Math.pow(2,this.maxDepth-1);
        this.gridMinWidth = conWidth / tmp;
        this.gridMinHeight = conHeight / tmp;
        //初始化层级size
        for(let i=0; i < this.maxDepth; i++){
            this.depthSize.push(new QPoint(conWidth/Math.pow(2,i),conHeight/Math.pow(2,i)));
        }
        this.quadTreeNode = new QuadTreeNode(originX,originY,0,this);
    }

     /**
      * 更新四叉树
      * @param item 
      * @param rect 
      */
    update(item:T,rect:QRect){
        this.quadTreeNode.update(item,rect);
    }
    
    /**
     * 查询碰撞节点
     * @param rect 
     * @param outItms 接收数组
     * @param outVisItms 访问过的节点
     */
     quary(rect:QRect,outItms:T[],outVisItms:T[]){
        this.quadTreeNode.quary(rect,outItms,outVisItms);
     }
}
